package nan.Hash_Tree;

class HashNode{
    public int key;
    public int value;
    HashNode next;

    public HashNode(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

public class HashMap {
    //哈希表的核心是有一个数组，数组上的每个元素又是一个链表
    private HashNode[] array=new HashNode[16];
    private int size=0;
    private int hashCode(int key){
        //通过这个方法，把key映射成数组下标
        return key%array.length;
    }
    //核心方法
    public void put(int key,int value){
        //1.先根据key计算下标位置
        int index=hashCode(key);
        //2.看key是否在hash表中存在,存在就直接修改value，不存在就直接插入新节点
        for(HashNode cur=array[index];cur!=null;cur=cur.next){//遍历index下标上的链表
            if(cur.key==key){
                //这就说明找到了相同key的元素
                cur.value=value;
                return;
            }
        }
        //头插
        HashNode newNode=new HashNode(key,value);
        newNode.next=array[index];//array[index]相当于头结点
        array[index]=newNode;
        size++;
    }
    //如果持续插入，就可能导致冲突概率越来越大，链表越来越长
}
